package com.future;

/**
 * Description: NC164 最长上升子序列(二) (注意：NC163 的优化版本 300. 最长递增子序列)
 *
 * @author weiruibai.vendor
 * Date: 2022/7/29 14:49
 */
public class Solution_NC164 {

    public static void main(String[] args) {
        Solution_NC164 nc164 = new Solution_NC164();
        int[] nums = new int[]{1, 3, 6, 7, 9, 4, 10, 5, 6};
        nums = new int[]{1, 4, 7, 5, 6};
        System.out.println(nc164.LIS(nums));
    }

    /**
     * 很重要，必须要会
     * eg:arr={1, 3, 6, 7, 9, 4, 10, 5, 6}
     * --------0  1  2  3  4  5  6   7  8
     * 初始时：end[0]=arr[0]=1,R=0(R可以认为是end有效的范围内的长度-1)
     * 从下标为1开始遍历
     * i=1
     * 从0~0(即0~R)通过二分查找，从end数组中找到比arr[1]小的最右侧位置+1，明显是下标为1，更新值为end={1,3},R=1
     * i=2
     * 从0~1(即0~R)通过二分查找，从end数组中找到比arr[2]小的最右侧位置+1，明显是下标为2，更新值为end={1,3,6},R=2
     * i=3
     * 从0~2(即0~R)通过二分查找，从end数组中找到比arr[3]小的最右侧位置+1，明显是下标为3，更新值为end={1,3,6,7},R=3
     * i=4
     * 从0~3(即0~R)通过二分查找，从end数组中找到比arr[4]小的最右侧位置+1，明显是下标为4，更新值为end={1,3,6,7,9},R=4
     * i=5
     * 从0~4(即0~R)通过二分查找，从end数组中找到比arr[5]=4小的最右侧位置+1，明显是下标为3，更新值为end={1,3,4,7,9},R=4
     * i=6
     * 从0~4(即0~R)通过二分查找，从end数组中找到比arr[6]=10小的最右侧位置+1，明显是下标为5，更新值为end={1,3,4,7,9,10},R=5
     * i=7
     * 从0~5(即0~R)通过二分查找，从end数组中找到比arr[7]=5小的最右侧位置+1，明显是下标为3，更新值为end={1,3,4,5,9,10},R=5
     * i=8
     * 从0~5(即0~R)通过二分查找，从end数组中找到比arr[8]=6小的最右侧位置+1，明显是下标为4，更新值为end={1,3,4,5,6,10},R=5
     * 那么答案就是 R+1;
     *
     * @param a
     * @return
     */
    public int LIS(int[] a) {
        if (a == null || a.length == 0) {
            return 0;
        }
        int N = a.length;
        if (N == 1) {
            return 1;
        }
        int end[] = new int[N];
        end[0] = a[0];
        int R = 0;
        for (int i = 1; i < N; i++) {
            int num = a[i];
            int l = 0;
            int r = R;
            while (l <= r) {
                int m = l + ((r - l) >> 1);
                if (num >= end[m]) {
                    l = m + 1;
                } else {
                    r = m - 1;
                }
            }
            end[l] = num;
            R = Math.max(R, l);
        }
        return R + 1;
    }
}
